#include <iostream>
using namespace std;

template <class T>
struct BSTreeNode
{
	BSTreeNode<T>* _left;
	BSTreeNode<T>* _right;

	T _val;
	BSTreeNode(const T& val)
		:_left(nullptr)
		,_right(nullptr)
		,_val(val)
	{ }
};

template <class T>
class BSTree
{
	typedef BSTreeNode<T> Node;
public:
	bool find(const T& val)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_val < val)
			{
				cur = cur->_right;
			}
			else if (cur->_val > val)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}
		return false;
	}

	bool insert(const T& val)
	{
		if (_root == nullptr)
		{
			_root = new Node(val);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_val < val)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_val > val)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(val);
		if (val > parent->_val)
		{
			parent->_right = cur;
		}
		if (val < parent->_val)
		{
			parent->_left = cur;
		}
		return true;
	}

	void inorder()
	{
		_inorder(_root);
	}

private:
	void _inorder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}
		_inorder(root->_left);
		cout << root->_val << " ";
		_inorder(root->_right);
	}

private:
	Node* _root = nullptr;
};


int main()
{
	BSTree<int> t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.insert(e);
	}
	t.inorder();

	t.insert(11);
	t.insert(12);
	t.inorder();

	return 0;
}